import java.util.Scanner;

public class Test {
    //给定一个二叉树，判断它是否是平衡二叉树--方法1：此时的时间复杂度为O（n*n)
    public boolean isBalanced1(TreeNode root) {
        if (root == null){
            return true;
        }
        int leftHigh = getHigh(root.left);
        int rightHigh = getHigh(root.right);
        if (Math.abs(leftHigh - rightHigh) > 1){
            return false;
        }
        return isBalanced1(root.left) && isBalanced1(root.right);
    }
    //获取树的深度，该树的根节点为root
    public int getHigh(TreeNode root){
        if (root == null){
            return 0;
        }
        return Math.max(getHigh(root.left),getHigh(root.right))+1;
    }
    //给定一个二叉树，判断它是否是平衡二叉树--方法2：此时的时间复杂度为O（n)
    public boolean isBalanced2(TreeNode root){
        if (root == null){
            return true;
        }
        if (getHigh2(root) == -1){
            return false;
        }
        return isBalanced2(root.left) && isBalanced2(root.right);
    }
    //获取根的深度，该方法主要是针对降低判断平衡二叉树的时间复杂度所作的修改，此时返回的可能不是树的高度
    public int getHigh2(TreeNode root){
        if (root == null){
            return 0;
        }
        if (getHigh2(root.left) >= 0 && getHigh2(root.right) >= 0
                && Math.abs(getHigh2(root.left) - getHigh2(root.right)) <= 1){
            return Math.max(getHigh2(root.left),getHigh2(root.right));
        }else {
            return -1;
        }
    }
    //给你一个二叉树的根节点 root ， 检查它是否轴对称。
    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        return isSystemmetricChild(root.left,root.right);
    }
    public boolean isSystemmetricChild(TreeNode left,TreeNode right){
        if (left == null && right != null || left != null && right == null){
            return false;
        }
        if (left == null && right == null){
            return true;
        }
        if (left.val != right.val){
            return false;
        }
        return isSystemmetricChild(left.right,right.left) && isSystemmetricChild(left.left,right.right);
    }
    //编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串：
    // ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode node = createTree(str);
            inOrderTraversal(node);
        }
    }
    public static int i = 0;
    public static TreeNode createTree(String str){
        char ch = str.charAt(i);
        TreeNode root;
        if (ch != '#'){
            root = new TreeNode(ch);
            i++;
            createTree(str);
        }else {
            i++;
            return null;
        }
        return root;
    }
    public static void inOrderTraversal(TreeNode root){
        if (root == null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.println(root.val);
        inOrderTraversal(root.right);
    }
}
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }
}


